package liangtWorkSpace.mage;

/**
 * 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
 * <p>
 * 一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
 * <p>
 * 返回一对观光景点能取得的最高分。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-sightseeing-pair
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @ClassName MaxScoreSightseeingPair
 * @Description : 最佳观光组合
 * @Author : LiangT
 * @Date : 2020/6/17 11:34
 */
public class MaxScoreSightseeingPair {

    /**
     * 双重循环--数组达到一定大小回超时
     *
     * @param A
     * @return
     */
    public int maxScoreSightseeingPair(int[] A) {
        if (A == null) {
            return 0;
        }
        if (A.length < 2) {
            return A[0];
        }
        if (A.length == 2) {
            return A[0] + A[1] + 0 - 1;
        }
        int sum = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                int a = A[i] + A[j] + i - j;
                if (sum < a) {
//                    System.out.println(A[i]+"A[i]:"+A[j]+"A[j]:"+i+"i:"+j+"j:"+sum+"sum:");
                    sum = a;
                }
            }
        }
        return sum;
    }

    /**
     * 时间复杂度0（n）空间复杂度（1）
     * @param A
     * @return
     */
    public int maxScoreSightseeingPair2(int[] A) {
        int sum = 0;
        int mx = A[0] + 0;
        for (int j = 1; j < A.length; ++j) {
            sum = Math.max(sum, mx + A[j] - j);
            mx = Math.max(mx, A[j] + j);
        }
        return sum;
    }

    public int maxScoreSightseeingPair1(int[] A) {
        int sum = Integer.MIN_VALUE;
        int mx = A[0];
        for (int j =1;j < A.length;++j){
            sum = sum>A[j]-j+mx?sum:A[j]-j+mx;
            mx = mx>A[j]+j?mx:A[j]+j;
        }
        return sum;
    }
    public static void main(String[] args) {
        int[] ints = {8, 1, 5, 2, 6};
        MaxScoreSightseeingPair maxScoreSightseeingPair = new MaxScoreSightseeingPair();
        System.out.println(maxScoreSightseeingPair.maxScoreSightseeingPair(ints));
    }
}
